接下來的五天我們會用不同的方式來解這題題目Sort an Array，一起來複習跟朝拜大師們想出來的排序法！
從前面開始有關input給了一個array的題目時，我們就很常看到sort，所以我們當然不能忽略sort的重要性。
今天來談大家一定要聽過的 Bubble Sort，雖然它不是最好的解法，但覺得不能被遺忘的經典。

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Bubble sort 其實就是從頭到尾拜訪每個元素，兩個兩個比較。兩個數比較後，如果大的在前面就把大的往後移。
同理也可以說小的在後面不斷把小的往前移。
以範例來說

[5,2,3,1]

1. 因為 5 > 2 , 所以 要交換位置 變成 [2 , 5 , 3, 1]
2. 因為 5 > 2 , 所以 要交換位置 變成 [2 , 3 , 5, 1]
3. 因為 5 > 1 , 所以 要交換位置 變成 [2 , 3 , 1, 5]

以上是第１回檢查 我們總共交換了三組的比較

接著我們進行第2回

1. 因為 2 !> 3,不動
2. 因為 3 > 1 , 所以 要交換位置 變成 [2 , 1 , 3, 5]
3. 因為 3 !> 5, 不動

等等！想一下，第6個步驟我們有需要做嗎？
觀察第一回合的檢查，我們其實就是把最大的數移到最右邊了

也就是說，我們走完第一回合，也確定最後一個數會是最大的。
我們第二次的檢查其實就可以少1次的比較，雖然少1次對我們時間複雜度的分析幫助不大。
因此跳過上面的6，繼續來看第三回
而這一回合我們就知道只剩下 2 和１需要比較，最後可以得到[ 1, 2 ,３, 5]

那我們什麼時候要停止檢查？
最簡單的原則就是：如果這回合沒有任何的交換 就代表array已經按照我們想要的順序排列了！

時間複雜度的分析：最糟的情況 Ｏ(n^2)，像是遇到[5,4,3,2,1]這種
而最好的情況就是 Ｏ(n), 遇到 [1,2,3,4,5] ，檢查一次就可以停止了。

空間複雜度，以上面例子，我們其實都在對同１個陣列做操作（交換）的行為，這種方式稱作 in place, 不需要另外的空間來暫存結果，所以是O(1)。

原地演算法（in-place algorithm，也稱「就地演算法」）是基本上不需要藉助額外的資料結構就能對輸入的資料進行變換的演算法 - wiki

最後來看javascript的實作吧

const bubbleSort = (array) => {
  // 一開始array 沒被sort
  let sorted = false;
  // counter來記錄我們檢查了幾回
  let counter = 0;
  while (!sorted) {
    sorted = true;
    // 扣除counter因為我們已經確定每次檢查最大數會在後面 可以省略檢查
    for (let i = 0; i < array.length - 1 - counter; i++) {
      if (array[i] > array[i + 1]) {
        swap(i, i + 1, array);
        // 只要有交換的行為發生 sorted就要設為還沒sorted完 才會再進入到while裡檢查
        sorted = false;
      }
    }
    counter++;
  }
  return array;
};

// 交換的function
const swap = (i, j, array) => {
  const tmp = array[j];
  array[j] = array[i];
  array[i] = tmp;
};

明天來實作 Insertion sort 和 Selection sort